package dp.子序列;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 摆动序列376.java
 * @createTime 2024年03月25日 19:00:00
 */
public class 摆动序列376 {
	/*
   状态：前面的差值，第i个数

   定义dp[i][0/1]表示第i个位置，以0降序，和以1升序结尾的最长子序列的长度

   当i>i-1时
   dp[i][0]=dp[i-1][0];
   dp[i][1]=dp[i-1][0]+1;
   当i<i-1时
   dp[i][0]=dp[i-1][1]+1;
   dp[i][1]=dp[i-1][1];
   当i=i-1时
   dp[i][0]=dp[i-1][0];
   dp[i][1]=dp[i-1][1];

   baseCase：
   dp[0][1]=0;
   dp[0][0]=0;
	*/
	public int wiggleMaxLength(int[] nums) {
		int[][] dp = new int[nums.length][2];
		dp[0][1] = 0;
		dp[0][0] = 0;
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] > nums[i - 1]) {
				dp[i][0] = dp[i - 1][0];
				dp[i][1] = dp[i - 1][0] + 1;
			} else if (nums[i] < nums[i - 1]) {
				dp[i][0] = dp[i - 1][1] + 1;
				dp[i][1] = dp[i - 1][1];
			} else {
				dp[i][0] = dp[i - 1][0];
				dp[i][1] = dp[i - 1][1];
			}
		}
		return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]) + 1;
	}
}
